iT邦幫忙

2024 iThome 鐵人賽

DAY 21
0

2024/09/21 Leetcode Daily Problem

386. Lexicographical Numbers
難度: 中等

題意

給定一整數n,回傳一整數陣列,值為1~n按照字典序(lexicographical)排列。

思路

題目直接說明要O(N)算法,因此自己寫字點序比較來排序應該是不能過。
我們要直接按照順序來產生,仔細觀察如下:

1 -> 10 -> 100 ...
        -> 101
        -> 102
        -> 103
        -> ...
        -> 109
  -> 11 -> 110
        -> 111
        -> 112
        -> ...
  -> 12 -> 120
        -> 121
        ...
  ...
  -> 19 -> 190
        -> 191
  ...
2 -> 20 -> 200 ...
        -> 201
        ...

是不是很像DFS~~

因此按照9~1的順需塞入堆疊中,這樣就可以從1先拿出來。
找出他的小孩,也就是乘十,再加9~1塞入堆疊中。
依此類推

實作

先做了兩版brute force生成的方法,結果都有順序錯誤,領了WA。
仔細觀察後決定用堆疊來存發生順序,避免出錯。

class Solution
{
public:
    vector<int> lexicalOrder(int n)
    {
        vector<int> res;
        if (n <= 0)
            return res;

        stack<int> st;
        for (int i = 9; i >= 1; i--)
            st.push(i);

        // DFS
        while (!st.empty())
        {
            int curr = st.top();
            st.pop();
            if (curr <= n)
                res.push_back(curr);

            curr *= 10;
            if (curr <= n)
            {
                // Add new children
                for (int i = 9; i >= 0; i--)
                    if ((curr + i) <= n)
                        st.push(curr + i);
            }
        }
        return res;
    }
};

分析

時間複雜度: O(N),DFS
空間複雜度: O(N),stack所需,但好像最多放logN?

總結

Time Submitted Status Runtime Memory language
09/21/2024 12:56 Accepted 12 ms 13.7 MB cpp
09/21/2024 12:20 Wrong Answer N/A N/A cpp
09/21/2024 12:17 Wrong Answer N/A N/A cpp

上一篇
[9/20] 加前綴變成回文
下一篇
[9/22] 1~n字典序的第k個
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言